package demo;

import java.util.Arrays;

/**
 * 下一个排列
 * 其实就是从数组倒着查找，找到nums[i] 比nums[i+1]小的时候，
 * 就将nums[i]跟nums[i+1]到nums[nums.length - 1]当中找到一个最小的比nums[i]大的元素交换。
 * 交换后，再把nums[i+1]到nums[nums.length-1]排序，就ok了
 */
public class Solution45 {
	public void nextPermutation(int[] nums) {
		if(nums == null || nums.length == 1) {
			return;
		}
		// 从后往前找
		int right = nums.length - 1;
		while(right > 0) {
			// 找到一个比后面数字小的
			if(nums[right] > nums[right - 1]) {
				// 后面数字的最小值
				int min = nums[right];
				int k = right;
				for(int j = right + 1; j < nums.length; j++) {
					// 该最小值要比nums[right-1]大，这样才可以交换
					if(nums[j] < min && nums[j] > nums[right-1]) {
						min = nums[j];
						// 标记最小值的位置，以便交换
						k = j;
					}
				}
				swap(nums, right - 1, k);
				// 对交换后,right-1之后的数组排序
				Arrays.sort(nums, right, nums.length);
				break;
			}
			right--;
		}

		// 降序数组直接重排
		if(right == 0) {
			Arrays.sort(nums);
		}
	}

	private void swap(int[] nums, int i, int k) {
		int tmp = nums[i];
		nums[i] = nums[k];
		nums[k] = tmp;
	}
}
